Print the shipping info on normal paper, then wrap it and the portion of tire under it completely in tape. So you'll use like 3 feet of tape or so depending on the tire width and how small your printed piece of paper is.
I never had a problem shipping tires that way. I used to use UPS just because it was closer to the house I shipped from than a FedEx place.